package 第6周_快速排序法.第一章快速排序法;

import 第1周_线性查找法.测试算法性能.ArrayGenerator;
import 第2周_排序基础.第一章选择排序法.SortingHelper;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    private QuickSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        if (l >= r){
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     *
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return 返回标定点的索引
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r){

        //生成[l, r]之间的随机索引
        int p = (new Random()).nextInt(r - l + 1) + l;
        swap(arr, l, p);

        //arr[l + 1, j] < v; arr[j + 1, i] >= v
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0){
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }

    /*
        双路快速排序法
     */
    public static <E extends Comparable<E>> void sort2ways(E[] arr){
        sort2ways(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r){
        if (l >= r){
            return;
        }
        int p = partition2(arr, l, r);
        sort2ways(arr, l, p - 1);
        sort2ways(arr, p + 1, r);
    }

    /**
     *
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return 返回标定点的索引
     */
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r){

        //生成[l, r]之间的随机索引
        int p = (new Random()).nextInt(r - l + 1) + l;
        swap(arr, l, p);

        //arr[l + 1 ... i - 1] <= v;  arr[j + 1] >= v
        int i = l + 1, j = r;
        while (true){
            //和标定点进行比较
            while (i <= j && arr[i].compareTo(arr[l]) < 0){
                i++;
            }

            while (j >= i && arr[j].compareTo(arr[l]) > 0){
                j--;
            }

            //如果i == j 说明 i 和 j 同时指向了一个和标定点一样的值
            if (i >= j){
                break;
            }

            swap(arr, i, j);
            i++;
            j--;

        }
        swap(arr, l, j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int n = 1000000;

        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        System.out.println("Random Array: ");
        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("QuickSort2Ways", arr2);

    }
}
